Magnum One

home *** CD-ROM | disk | FTP | other *** search

/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / flcpp2.arc / FLEXLIST.DOC < prev next >

Wrap

Text File | 1990-12-07 | 38.5 KB | 853 lines

FlexList II for C++ Copyright 1990 John W. Small All rights reserved PSW / Power SoftWare P.O. Box 10072 McLean, Virginia 22102 8072 (703) 759-3838 11/28/90 CLAIM TO PROPRIETARY TECHNIQUES Several features of FlexList used in combination make FlexList unique and versatile. The hybrid stack-queue-list-array data structure and the techniques used to implement it as a generic polymorphic object can be easily ported to other computer languages and remain intact in their essence. The author claims all rights to these features. SHAREWARE NOTICE This FlexList packet is offered to you as "shareware" meaning try before you buy. The shareware version allows you to test the product to see if it's suitable for your purposes. In order to legally use FlexList for any other purpose than to evaluate it, you must first license it from PSW / Power SoftWare by sending in a registration fee of $79.95. Upon registration you will receive a printed version of the complete manual and source code. SHAREWARE MANUAL The shareware documentation that follows has been taken from the actual printed FlexList manual. I've include only the most vital information. Refer to flexlist.hpp for FlexList member function prototypes. Introduction FlexList II is a lot more than just a ready-to-run C++ linked list. It's a searchable-sortable-implodable generic heterogeneous-homogeneous hybrid stack-queue-list-array accessible by value, reference or node. Anytime your C++ application requires a stack, queue, or linked list, simply include flexlist.hpp in your source code and then start defining your stack, queue, and/or list variables as type FlexList. A FlexList can be initialized, by constructor, to store any type of data and then accessed as a stack, queue, list, or even an array interchangeably! With more than 30 FlexList member functions to choose from, you can push, pop, insert, delete, sort, store, recall, or find, to name but a few. Access your data by value (copy) or by reference (pointer). Or move nodes directly between FlexLists. Because FlexList member functions adjust automatically to different types of data, new sets of primitives needn't be derived to accommodate new data types. Thus your application's coding time and code size won't continue to grow when you add new types of FlexLists. A FlexList can even be made to accommodate heterogeneous data via its virtual member function hooks. With FlexList you can quickly construct lists of lists or other composite structures. And since FlexLists are initialized at run time, the data they hold or even their creation can be specified at run time thus allowing your application new dimensions of adaptability to user inputs. Use FlexList to code your next application's linked lists in minutes instead of days, without the usual debugging and documenting headaches associated with custom coding various list types. It's no problem modifying your application in midstream to incorporate various and differing list types; with FlexList no linked list code needs to be scrapped or rewritten. The code space you'll save over cloning list primitives for different data types may just save you from having to go the overlay/swapping route. Chapter 2. Programming with FlexList This chapter is a combination of a brief tutorial on using the FlexList tool and a logical survey of the FlexList functions. You may find it useful to lookup the FlexList functions in the reference chapter while reading the example programs here. Don't worry too much about the details for now. Instead you should finish this chapter with 1) an idea of the points to remember when programming with FlexList, 2) a conceptual model of FlexList's hybrid stack-queue-list- array data structure, and 3) an appreciation for the various ways that a FlexList can be manipulated and accessed, namely: by value, by reference, or by node. After programming for a while with FlexList, be sure to reread this chapter. Let's first cover several points that you should keep in mind when using FlexList in any application. 1. Include flexlist.hpp in any application using FlexList. #include <flexlist.hpp> 2. Define your stack, queue, or list as a FlexList, specifying the size of the data it is to hold. To construct a FlexList for stack of integers the code is: FlexList intStack(sizeof(int)); 3. The address of your data must be passed to FlexList member functions. Remember, don't pass the data by value. for (int i = 1; i < 11; i++) intStack.pushD(&i); // address of i 4. FlexList member functions return pointers or integers. A returned value of zero indicates failure of the function to carry out its task. while (intStack.popD(&i)) // loop until false cout << i << "\n"; 5. Don't forget to link your application with the object module created by compiling flexlist.cpp or with the library you build. Let's see the whole program. #include <iostream.h> // cout #include <flexlist.hpp> main() // Count backwards from ten via a stack. { FlexList intStack(sizeof(int)); for (int i = 1; i < 11; i++) intStack.pushD(&i); while (intStack.popD(&i)) cout << i << "\n"; } Let's proceed with a survey of FlexList member functions. FlexList Constructor/Destructor Functions The FlexList class has two constructors and a virtual destructor. FlexList(size_t sizeofNodeData, unsigned maxNodes = FLmaxMaxNodes); FlexList(unsigned sizeofCell, unsigned cells, const void *array); int clear(); // discards all FlexNodes in FlexList virtual ~FlexList() { clear(); } The first constructor you have already seen. It has a defaulted second parameter that lets you set an upper limit on the number of FlexNodes the FlexList is allowed to hold. FLmaxMaxNodes is defined in flexlist.hpp as the maximum value an unsigned int can obtain. What's not obvious is if you construct a FlexList with the sizeofNodeData parameter equal to zero you bring FlexList's virtual functions into play that allow the FlexList to work with variant data. The virtual functions in the FlexList base class are set up to work with strings. Let's say you code the following: #define FLvariantData 0 #define FLstrings FLvariantData FlexList strStack(FLstrings); (FLvariantData and FLstrings are defined in flexlist.hpp.) The FlexList will now work with strings. The FlexNodes will be just big enough to hold strings within. If you derive a class from FlexList and override the virtual functions then your derived class can accommodate any type of object you want it to (see the FlexList constructor entry in the reference chapter). The second constructor allows you to explode a conventional C++ array (vector) into a FlexList. The FlexList destructor is virtual so that your derived classes can be destructed from code written to work on FlexLists. Such is the case with composite FlexList structures. FlexList Header Access Functions As you become more familiar with what's inside a FlexList you will want to access the data fields inside the FlexList header. frontD() currentD() rearD() CurNum() Nodes() MaxNodes() setMaxNodes() notFull() SizeofNodeData() isSorted() unSort() Compare() setCompare() isFixed() isVariant() A FlexList can be accessed as a stack, queue, list, or even an array once it has nodes in it, interchangeably. The FlexList header keeps track of everything so if your pushing data onto your "stack" at one moment, you can recall an element from your "array" the next. You can sort your FlexList, then perform various other operations on it and isSorted will tell you if it is still sorted. You can set an upper limit on the number of nodes a FlexList is allowed to hold with setMaxNodes. You will come to know what each function does with time. FlexList Stack and Queue Functions A stack provides LIFO (Last In, First Out) storage. A complete set of stack primitives is provided. These functions don't disturb the queue, list, or array structure of a FlexList. In other words, you can access your FlexList as a stack at any time and revert back to accessing it as a queue, list, or array freely. pushN() pushD() popN() popD() topD() insQN() insQD() frontD() rearD() A queue provides FIFO (First In, First Out) storage. Notice that some of the stack functions double up here as queue functions, e.g. popD, topD. Also I have again included some of the FlexList header access functions, i.e. frontD and rearD which return pointers to the data in the first and last nodes respectively. Basically I'm suggesting various logical ways to categorize FlexList functions to help you remember them. You'll find that several functions may belong in multiple categories. The functions ending with "N" work directly with the FlexNodes which contain your data. For an example, suppose that you want to pop your stack directly into your queue. The following code shows how. #include <iostream.h> // cout #include <flexlist.hpp> int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int *iptr; #define inT0 ((int *)0) main() /* count to ten the hard way */ { FlexList s(sizeof(a[0]),sizeof(a)/sizeof(a[0]),a); FlexList q(s.SizeofNodeData()); while ((iptr = (int *) q.insQN(s.popN())) != inT0) cout << *iptr << "\n"; } In this example the stack is constructed by "exploding" an array of integers into a FlexList. Next the queue is constructed to hold the same size data as the stack. Then the stack is popped directly into the queue and a pointer to the data in the newly inserted queue node is captured and tested to control the looping! I print the integer each time so you can see that it made it into the queue. Did you notice how I defined the NULL integer pointer? I did that here so you'll know what's going on when you see other NULL pointers elsewhere. FlexList List Functions Any FlexList can be treated as a doubly linked list thereby providing sequential storage. You can insert nodes or delete them. The FlexList header maintains a current node pointer that lets the list functions know where the insertion or deletion is to take place. Stack and queue functions don't disturb this current pointer unless of course it points to the top/front of the stack/queue and that node is popped/removed. In that case the current node becomes undefined. mkcur() insN() insD() insSortN() insSortD() delN() delD() nextD() prevD() CurNum() currentD() Compare() setCompare() FlexList nodes are numbered starting at one. When nextD reaches the end of the list the current node number is set to zero which is said to be undefined and nextD returns the NULL void pointer. On the next call to nextD the current node becomes one, that is of course if there are nodes in the FlexList! PrevD works the same way. This mechanism makes it handy to walk around lists pausing at the ends. If you want to set the current pointer to a particular node, use mkcur. Oh, I guess I should mention again that you can store any type of data in a FlexList not just integers. Let's see something like that last example again with strings. #include <iostream.h> // cout #include <flexlist.hpp> char *a[] = { "Now is the time", "for all good", "programmers to cut", "their coding time", "with FlexList!" }; char **sptr; #define chaRR char ** #define chaRR0 (chaRR)0 main() // PSW propaganda { FlexList l(sizeof(a[0]),sizeof(a)/sizeof(a[0]),a); while ((sptr = (chaRR) l.nextD(0)) != (chaRR0)) cout << *sptr << "\n"; l.mkcur(l.Nodes()); while (l.delD(0)) /* null statement */; // l.clear(); cout << "\nThere should be zero nodes now: "; cout << l.Nodes(); } In this program I exploded a vector of char pointers into a FlexList. Whenever FlexLists are constructed the current node is set as undefined so nextD starts walking across the FlexList beginning with the first node. NextD will copy the data in the next node to whatever address you specify for the parameter unless of course it is the NULL address! When you are browsing the reference chapter you will notice many FlexList functions that copy data to/from a FlexNode when an address is given. If the NULL address is specified the copying action is inhibited but the function otherwise performs its purpose. In this example nextD is inhibited from copying any data but it never the less moves the current pointer on to the next node. NextD also returns a void pointer to the data in the next node. I capture that pointer in order to print the string but I'm also using it to control the loop. All FlexList functions return either pointers or integer types that are non zero only when the respective function completes successfully. The void pointers returned from FlexList functions point to the user data in focus. In the case of nextD it points to the user data in the next node. I have simply type casted this pointer to a pointer to the type of data I'm storing in the FlexNodes in order to gain access to that data. As you can see FlexList member functions allow you to access you data by value (copy) or by reference (pointer) as well as moving nodes directly between/within FlexLists. Back to our example, mkcur moves the current node pointer to the last node in the list. Mkcur also returns a pointer to the data in the last node but I choose to ignore it. Now delD is used to delete the nodes from the list. DelD removes the current node after copying its contents to the address specified (copying is inhibited here by the NULL address) and then unlinks the FlexNode from the FlexList and proceeds to deallocate it making the previous node in the FlexList the new current node. I might add that insD does the exact opposite, i.e. inserts a new FlexNode after the current node making the new node current. Again the stack and queue structure of FlexList is undisturbed by any list functions invoked on the FlexList and vice versa. FlexList Search/Sort Functions The Search/Sort functions allow you to lookup and/or sort your data. Every FlexList has a user definable compare function. Use setCompare to set a FlexList's internal compare function pointer. To facilitate sorting define your compare function to return -1, 0, or 1 to indicate whether the first data being compared is less than, equal to, or greater than the second, respectively. The compare function is also used for matching in the find...() functions. Please note that most of the functions mentioned here modify the current node setting, thus they interact with the list functions mentioned earlier. insSortN() insSortD() findFirstD() findNextD() findLastD() findPrevD() sort() isSorted() unSort() Compare() setCompare() Use insSortD/N() to perform insertion sorts. If the list isn't sorted then sort will be called automatically before attempting the insertion. If a compare function pointer hasn't been setup then the insertion is aborted. The find...D functions work regardless if the FlexList is sorted or not. If it is sorted then the binary search algorithm is used to find the first/last matching data and a linear search is used to find the next/previous match stopping immediately after the first mismatch. If the FlexList is not sorted then the linear search algorithm is used to find the first/last matching data and again to find the next/previous match stopping only at the ends of the list. Use sort or setCompare to setup the compare function pointer. If the NULL compare function pointer, FLcompare0 (defined in flexlist.hpp), is passed to sort then the previous compare function pointer is used to sort the list. Call isSorted to determine whether a FlexList is still sorted from its last sort. For example, suppose you sort a list and pop some nodes off the front. Well that won't cause the FlexList to be unsorted so isSorted will return true. But if you push some data onto it treating it like a stack, that may or may not ruin the sorted order. IsSorted will return false because it can no longer guarantee that the FlexList is sorted. You need to be careful though since nextD, prevD, and mkcur won't cause isSorted to reset to false even though you might have modified the data in the FlexNode via the returned void pointer! In that case you may want to call unSort to reset isSorted so that it will return false. The following example performs an unsorted linear search followed by an alphabetical sort. #include <iostream.h> // cout #include <string.h> // strstr, strcmp #include <flexlist.hpp> int strStr(char *s, char *t) { return !(int)strstr(s,t); } main() { FlexList l(FLstrings); char *s, sbuf[80]; char *mask = "overtime"; l.insD("Once upon a time there were three"); l.insD("programmers, who worked"); l.insD("allot of overtime!"); l.insQD("That was before the FlexList Fox"); l.insQD("joined the staff!"); for (l.mkcur(0); l.nextD(sbuf);/* no reinit */) cout << "\n Node: " << l.CurNum() << ". " << sbuf; l.setCompare(FLcomparE(strStr)); if ((s = (char *)l.findFirstD(mask)) != (char *)0) { cout << "\n Mask: \"" << mask << "\""; cout << " found in node: " << l.CurNum(); cout << ". " << s; } l.sort(FLcomparE(strcmp)); for (unsigned i = 1; l.recallD(sbuf,i); i++) { cout << "\n Node: " << l.CurNum(); cout << ". " << sbuf; } } This program constructs a variant FlexList. The FlexNodes in this FlexList are only be enough to hold the character strings passed as parameters (please note that character string constants are pointers to the strings so I didn't use the address of, "&", operator!) I didn't use the second constructor because it builds fixed size FlexNode (homogeneous) FlexLists - an array has fixed cell sizes. Instead I inserted the strings one by one and queued the last two just to be different. The first "for loop" uses nextD to verify the contains of the FlexNodes. NextD only copies the string and zero terminator thanks to the virtual functions (see FlexList constructor entry in the reference chapter to see how to construct heterogenous lists). Be sure that the variable whose address you pass to nextD is big enough to accommodate the largest data that can be read! You should have noticed that I had to use mkcur(0) since the current node pointer is still pointing to the last node inserted and not the last node queued. Remember, queue functions don't disturb the list structure - the current node concept is part of the list structure, not the queue structure! Since the list is not sorted, findFirstD searches in a linear fashion starting with the first node, internally calling the compare function setup with setCompare. The FLcomparE macro, defined in flexlist.hpp, type casts strStr to the precise function pointer type required by both setCompare and sort. My strStr returns 0 if t is within s. Since only a linear search will be used with this compare function, it doesn't matter that is doesn't return -1 or 1 to indicate less than or greater than. The program proceeds with a standard alphabetical sort and the resultant ordering is displayed with recallD, an array access function which you'll see in the next section. FlexList Array Functions An array provides randomly accessible storage. A FlexList can also be accessed as an array once it has nodes in it. storeD() recallD() mkcur() currentD() CurNum() The last node accessed becomes the new current node. When randomly accessing a FlexList, mkcur is called internally by both storeD and recallD to make the requested node current. Mkcur determines which pointer (front, current, or rear) is closest to the requested node. It then follows the FlexList's linkage from that closest pointer to the newly requested node. The current pointer is left positioned at the new node. Please note that array, search/sort, and list functions interact in that they all work with and modify the current node setting. Stack and queue functions are independent, however. FlexList Compaction Functions Sometimes you want to work with a list, other times it's more convenient to work with an array. Although FlexList allows this chameleon behavior, your application may progress in stages that favor a linked list at one point and a conventional array (vector) at another. FlexList has "compaction" functions for converting a FlexList into a conventional array or vice versa, thus allowing you to optimize the performance of your application. FlexList() pack() packPtrs() You can think of the second FlexList constructor as exploding a conventional array into a FlexList. Think of the pack member function as doing the exact opposite or imploding a FlexList into a conventional array. Arrays compacted by pack and packPtrs must be explicitly deleted with a call to delete when no longer needed if their memory is ever to be recovered for subsequent reuse. PackPtrs returns an array of void pointers pointing to the data in the FlexNodes. This array is NULL terminated to facilitate subsequent processing. For the last example program we'll clone a vector of char pointers but the clone will have the advantage over its parent of being sorted in alphabetical order. #include <iostream.h> // cout #include <string.h> // strcmp #include <flexlist.hpp> char *a[] = { "one", "two", "three", "four", "five" }; char **A; int strCmp(char **s, char **t) { return strcmp(*s,*t); } main() { FlexList l(sizeof(a[0]),sizeof(a)/sizeof(a[0]),a); l.sort(FLcomparE(strCmp)); A = (char **) l.pack(); for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++) cout << "\n a[" << i << "] = " << a[i]; if (A) { for (i = 0; i < l.Nodes(); i++) cout << "\n A[" << i << "] = " << A[i]; delete A; } } Remember that the FlexNodes in this program contain char pointers and that the compare function is passed pointers to the char pointers, that is why the strCmp has to dereference them. Many commercial toolbox functions require vector parameters. With FlexList's compaction functions you can manipulate vectors on the fly. The vectors can be stored in files and loaded as needed via a FlexList and subsequent packing. The vector can then be kept around only during the computation phase in which it is needed. Large, oversized, static vectors need not be allocated at compile time to cope with worst case scenarios, consequently consuming precious data segment space within your program. Accessing FlexList Nodes and Data Now that we've finished categorizing FlexList functions along the lines of its hybrid stack-queue-list-array structure, let's rethink what we've seen in terms of how the FlexList was accessed, namely: by value, by reference, and by node. This gives us a second way to analyze FlexList functions. "By value" implies that the data is copied to or from a FlexNode. For example, with popD the top node of the stack is popped and the data is copied to the address specified by the parameter before the node is freed and returned to the heap. We are in effect accessing the data in the top node by value since we are retrieving, in actuality, a copy of it. popD(&i); // i is same type in FlexNode "By reference" implies that the data in the FlexNode is accessed by pointer. You will need to type cast these void pointers to pointers to the type of data you have stored in the FlexNodes. Suppose we're walking backward across a FlexList of integers with the code: while ((iptr = (int *)l.prevD(0)) != (int *)0) cout "\n" << *iptr; All void pointers returned by FlexList functions point to user data. Thus the data can be modified directly. "By reference" functions are provided to speed up processing. Without pointer access you would have to first copy the data out of the FlexNode, modify it and then copy it back. With large data structures that could prove to be quite inefficient. Please note the nextD and prevD are purely "by reference" when called with their parameters equal to the NULL address. Actually all FlexList functions returning void pointers allow access "by reference" in combination perhaps with "by value" access. In queuing network simulations you will want to move nodes between FlexLists rapidly. Without access "by node" you would have to "popD" the source queue and "insQD" the destination queue. This would entail copying the data from the front node into a local variable of the same type, unlinking and deallocating the FlexNode, then reallocating a new FlexNode and linking it into the other queue and finally copying the data from the local variable back into the node. The faster way is to unlink the FlexNode from the source queue and relink it directly into the destination queue, e.g. dstQ.insN(srcQ.popN()); If dstQ is already full then the node popped from srcQ is lost in the twilight zone. A better approach would be to prevent the chance of FlexNodes being left dangling: while (dstQ.notFull() && srcQ.Nodes()) dstQ.insN(srcQ.popN()); The "By node" functions unlink and relink FlexNodes directly between compatible FlexLists. Compatible in this sense means that both FlexLists have equal sizeofNodeData fields (not necessarily initialized for the same data type) . Use the SizeofNodeData function to read the sizeofNodeData field. Two FlexLists could also be considered to be compatible if they are both variant FlexLists with compatible data. I should point out that variant FlexLists have the sizeofNodeData fields set to zero. Be careful not to assume that two FlexLists are compatible just because both sizeofNodeData fields are equal to zero. You are responsible for insuring that your FlexLists are compatible. Remember also, FlexNodes unlinked with a function ending with "N" must be relinked with a function ending with "N" to a compatible FlexList or otherwise explicitly disposed of. Summary Let's review what we learned starting with the points to remember when programming with the FlexList tool. 1. Be sure to include the FlexList header in any module that references FlexList functions. 2. Define your stacks, queues, lists, etc. as "FlexList". Define your dynamic versions as pointers to FlexLists, i.e. "FlexL". 3. If the function is somehow involved with the copying of user data, the address of the data is always passed. 4. All FlexList member functions return either pointers or integers. A returned value of zero indicates failure of the function to complete its task. 5. Link your application with the compiled flexlist object module or the flexlist library you build. Next, let's review the various functions available in the FlexList tool. FlexList functions can be categorized according to the logical nature of a FlexList's inherent hybrid stack- queue-list-array structure. FlexList Constructor/Destructors FlexList() FlexList() clear() ~FlexList() FlexList Header Access Functions frontD() currentD() rearD() CurNum() Nodes() MaxNodes() setMaxNodes() notFull() SizeofNodeData() isSorted() unSort() Compare() setCompare() isFixed() isVariant() FlexList Stack and Queue Functions pushN() pushD() popN() popD() topD() insQN() insQD() frontD() rearD() FlexList List Functions mkcur() insN() insD() insSortN() insSortD() delN() delD() nextD() prevD() CurNum() currentD() Compare() setCompare() FlexList Search/Sort Functions insSortN() insSortD() findFirstD() findNextD() findLastD() findPrevD() sort() isSorted() unSort() Compare() setCompare() FlexList Array Functions storeD() recallD() mkcur() currentD() curNum() FlexList Compaction Functions FlexList() pack() packPtrs() Finally, FlexLists can be accessed "by value", "by reference", and "by node." "By value" entails the copying of user data between the FlexNodes and user specified addresses. If the address specified is NULL then the copying of data is inhibited but the function performs otherwise as expected. The address is always the first parameter of the FlexList function requiring it. "By reference" infers that user data is manipulated directly inside a FlexNode via a pointer. All FlexList functions returning void pointers allow "by reference" access. "By node" functions allow FlexNodes to be yanked/inserted from/into FlexLists. These functions are named with "N" suffixes. Move FlexNodes only between compatible FlexLists. Don't leave FlexNodes dangling: either insert them back into a compatible FlexList with an "N" function or explicitly delete them. By now you should be ready to start the planning and subsequent coding of your FlexList application with the help of the reference chapter on FlexList functions. Later, when you feel comfortable with FlexList, you will want to try your hand at deriving your own variant FlexLists (lists that contain heterogeneous data). Be sure to read the entry for the first FlexList constructor in the reference chapter for an explanation of writing your own FlexList virtual functions that accommodate your heterogeneous data.